\chapter{自上而下的语法分析}

    语法分析的任务: $\forall w\in V_T^*$, 判断$w\in L(G)$. 语法分析器是一个程序, 按照$\mathcal{P}$做识别$w$的工作.

    主旨: 从文法开始符号出发, 反复使用产生式, 自上而下为输入串建立一棵语法树. 也叫\textsf{推导--- 匹配法}. 

    自上而下的语法分析有两种基本方法: 回溯分析和预测分析.

    \section{自上而下分析面临的问题}

        语法树的构建需要回溯\footnote{因为都是确定机, 不是神机}. 开始时一无所知, 只能通过猜测的方法来匹配规则, parsing变为图搜索的过程, 可能会遇到虚假匹配(暂时的匹配).

        左匹配(最左深搜)遇到\textsf{左递归}的文法: $P\stackrel{+}{\Rightarrow}P\alpha, P\in V_N$会陷入无限循环. 最左宽搜遇到左递归文法会消耗指数级时间和空间, 实践中很少使用.

        难以报告出错的确切位置, 穷举效率低下.

        \subsection{消除文法的左递归}
        
            \textsf{左递归}的分类: 直接左递归 $N\to N\alpha$, 间接左递归$N\to A\alpha, A\to B\beta, B\to N\gamma$, 潜在左递归$N\to\alpha N, \alpha\stackrel{+}{\Rightarrow}\varepsilon$.

            \begin{algorithm}
                \caption{消除文法中的一切左递归}
                \label{algorithm-eliminate-all-left-recursion}
                \begin{algorithmic}[1]
                    \Procedure{Eliminate-All-Left-Recursion}{$G$}
                        \State 排序$\forall P_i \in G$
                        \For{$P_i\in V_N$}
                            \For{$j=1$ to $i-1$}
                                \State 将$P_j$代入$P_i$的产生式(若可代入)
                            \EndFor
                            \State 消除$P_i$的直接左递归
                        \EndFor
                        \State 化简所得文法
                    \EndProcedure
                \end{algorithmic}
            \end{algorithm}

            \subsubsection{消除直接左递归}

                候选式 $A\to A\alpha|\beta$可以匹配$\beta$, $\beta\alpha$, $\beta\alpha\alpha$, \ldots 替换为 $A\to\beta A', A'\to\alpha A'|\varepsilon$.

            \subsubsection{消除间接和潜在的左递归}

                \textsf{代入法}: 将一个产生式规则右部的$\alpha$中的非终结符$N$替换为$N$的候选式. 如果$N$有$n$个候选式, 右边的$\alpha$重复$n$次, 而且每一次重复都有$N$的不同候选式来代替$N$. \\
                示例: $N\to a|Bc|\varepsilon$在$S\to pNq$中的代入结果为$S\to paq|pBcq|pq$

        \subsection{克服回溯}

            如果条件允许, 用神机\footnote{明神的电脑, 计算模型是非确定机}来匹配文法是最简单的解决方案.

            \subsubsection{产生回溯的原因}

                匹配失败: 有多个$\alpha_i$以$a$开头, 这是文法的责任.

            \subsubsection{不回溯的条件}

                非终结符$A$的所有候选式的首符号($V_N$, 非终结符号)集合两两不相交.

                \paragraph{形式化} 定义FIRST$(\alpha)=\{a|\alpha\stackrel{*}{\Rightarrow}a\cdots, a\in V_T\}$, 若$\alpha\stackrel{*}{\Rightarrow}\varepsilon$, 规定$\varepsilon\in$ FIRST$(\alpha)$. 要求对于$\forall a\in$ FIRST$(\alpha_i)$, 则$a\not\in$ FIRST$(\alpha_j), j\neq i$.

                \paragraph{方法} \textsf{提取公共左因子}
                    若$A\to\delta\beta_1|\delta\beta_2|\cdots|\delta\beta_n|\gamma_1|\gamma_2|\cdots|\gamma_m$, 其中每个$\gamma$不以$\delta$开头. 那么可以将这些规则改写成$A\to\delta A'|\gamma_1|\gamma_2|\cdots|\gamma_m, A'\to\beta_1|\beta_2|\cdots|\beta_n$.

    \section{递归下降分析程序}

        \textsf{递归下降分析}: 将一个非终结符$A$的文法规则看作将识别$A$的一个过程的定义.

        最简单的情形, 要求不包含左递归且不会回溯, 即每一个文法的所有候选式的首符集两两不相交. 这样的分析程序叫做\textsf{递归下降分析器}.

        通过一组递归过程组成, 每个过程对应文法的一个$P_i\in V_N$. 递归好在直观和简单, 适合研究, 但是执行起来效率低.

    \section{预测分析程序}

        用一个分析表和一个栈来实现递归下降分析. 基于剩余输入, 预测使用产生式, 不回溯. 与状态转化矩阵对比: 及早发现错误, 缩减状态转化.\\
        特点: 快, 弱, 牺牲表达能力换取速度.

        \subsection{模型}

            \begin{description}
                \item[输入] 含有要分析的串, 以\#结尾
                \item[栈] 以\#为栈底, 栈内是一系列文法符号. 开始时, \#和$S$分别进栈
                \item[预测分析表] $V_N\times V_T$, 可以表示为$M[A,a], A\in V_N,a\in V_T$. 一般是压缩过的. \\
                    元素形式为$\{X\to UVW\}$, 也可以是error.
                \item[总控程序]
                \item[输出] 根据分析表内元素规定的语义动作
            \end{description}

        \subsection{工作过程}

            栈顶元素$X$和当前输入符号$a$决定一个\textsf{状态}, $(X,a)$决定程序的动作:
            \begin{itemize}
                \item $X=a=\#$, 分析完成
                \item $X=a\not =\#$, 弹栈, 后移输入指针
                \item $X\in V_N$, 查分析表$M[X,a]$, 认为该元素为$X$的产生式, 或出错 \\
                    先将$X$从栈顶弹出, 将$X$的产生式\textbf{反序}压入栈.
            \end{itemize}

                栈的实质: \uline{没有被匹配的}残缺的规范句型. 表的实质: 根据碰到的$V_T$元素指出$V_N$按哪条规则扩充成什么.

                缺点: 大量采用选择, 发现错误较晚.

        \subsection{如何产生预测分析表}

            \subsubsection{朴素方法} 循环机械填表(产生式/错误).

            \subsubsection{改进的方法} 将产生式分类, 找出产生式的规律:
                \begin{itemize}
                    \item 右部不是$\varepsilon$: $\alpha\stackrel{*}{\Rightarrow}a\cdots$\\
                        $A\to \alpha$, FIRST$(\alpha)=\{a_1,a_2\}$, 则可以填入$M[A,a_1]=M[A,a_2]=A\to\alpha$.
                    \item 右部是$\varepsilon$ \\
                        若一个符号``+''在句型中可以出现在$T'$的后面($a\in\mathrm{FOLLOW}(A)$), 则$T'$允许替换为$\varepsilon$
                \end{itemize}

                FIRST$(\alpha)=\{a|\alpha\stackrel{*}{\Rightarrow}a\cdots, a\in V_T\}$, 若$a\stackrel{*}{\Rightarrow}\varepsilon$, 规定$\varepsilon\in\mathrm{FIRST}(\alpha)$.

                FOLLOW$(A)=\{a|S\stackrel{*}{\Rightarrow}\alpha Aa\beta, a\in V_T, \alpha, \beta\in V^*\}$

            \subsubsection{构造FIRST$(\alpha)$}

                $\alpha=X_1X_2\cdots x_n$, 先构造FIRST$(X_i)$. 

                若$X\in V_T$, 则FIRST$(X)$是$\{X\}$. 
                
                若$X\in V_N$且$X\to a\alpha$, 则$\{a\}\cup \mathrm{FIRST}(X)$, 或$X\to \varepsilon$, 则$\{\varepsilon\}\cup \mathrm{FIRST}(X)$. 
                
                若$X\in V_N, X\to Y,\cdots, Y\in V_N$, 则FIRST$(Y)\backslash\{\varepsilon\}\cup \mathrm{FIRST(X)}$.

                \begin{algorithm}
                    \caption{产生产生预测分析表所需的FIRST集合和FOLLOW集合}
                    \label{algorithm-generate-predict-table}
                    \begin{algorithmic}[1]
                        \Function{First}{$X_i$}
                            \If{$X\in V_T$}
                                \State $X\in\mathrm{FIRST}(X_i)$
                            \ElsIf{$X\in V_N$}
                                \If{$X\to a\alpha$}
                                    \State $a\in\mathrm{FIRST}(X)$
                                \EndIf
                                \If{$X\to \varepsilon$}
                                    \State $\varepsilon\in\mathrm{FIRST}(X)$
                                \EndIf
                                \If{$X\to Y\cdots, Y\in V_N$}
                                    \State FIRST$(Y)\backslash\{\varepsilon\}\subset\mathrm{FIRST(X)}$
                                \EndIf
                            \EndIf
                        \EndFunction

                        \State \Function{First}{$X_1X_2\cdots X_n$}
                            \State ret\ $\gets\mathrm{FIRST}(X_1)\backslash\{\varepsilon\}$
                        \iffalse
                            \State flag\ $\gets$\ True, $i\gets$\ 1, ret\ $\gets\mathrm{FIRST}(X_1)\backslash\{\varepsilon\}$
                            \While{flag}
                                \ForAll{$P\in$ FIRST$(X_i)\backslash\{\varepsilon\}$}
                                    \State ret$\gets$\ ret$\cap\{P\}$
                                \EndFor
                                \If{$\varepsilon\not\in$ FIRST$(X_i)$}
                                    \State flag\ $\gets$\ False
                                \EndIf
                            \EndWhile
                        \fi
                            \ForAll{$\varepsilon\in\mathrm{FIRST}(X_j), 1\leqslant \forall j\leqslant i-1,$}
                                \State ret $\gets$\ ret $\cap\ \mathrm{FIRST}\backslash\{\varepsilon\}$
                            \EndFor
                            \If{$\varepsilon\in\mathrm{FIRST}(X_j), 1\leqslant \forall j\leqslant n$}
                                \State ret $\gets$\ ret $\cap\ \varepsilon$
                            \EndIf
                            \State \Return ret
                        \EndFunction

                        \State \Procedure{Generate-Follow}{}
                            \State $\#\in\textrm{FOLLOW}(S)$
                            \While{没有修改结束}
                                \If{$A\to \alpha B\beta$}
                                    \State $\textrm{FIRST}(\beta)\backslash\{\varepsilon\}\subset\textrm{FOLLOW}(B)$
                                \EndIf
                                \If{$A\to \alpha B\vee A\to \alpha B\beta\wedge \varepsilon\in\textrm{FIRST}(\beta)$}
                                    \State $\textrm{FOLLOW}(A)\subset\textrm{FOLLOW}(B)$
                                \EndIf
                            \EndWhile
                        \EndProcedure
                    \end{algorithmic}
                \end{algorithm}


            \subsubsection{再构造FIRST$(X_1X_2\cdots X_n)$}

                \begin{enumerate}
                    \item 将FIRST$(X_1)$的非$\varepsilon$终结符加入FIRST$(\alpha)$,
                    \item 若$\varepsilon\in$ FIRST$(X_1)$, 则将FIRST$(X_2)$的所有非$\varepsilon$终结符加入FIRST$(\alpha)$,
                    \item 若$\varepsilon\in$ FIRST$(X_1)$, $\varepsilon\in$ FIRST$(X_2)$, 则将FIRST$(X_3)$的所有非$\varepsilon$终结符加入FIRST$(\alpha)$,
                \end{enumerate}

            \subsubsection{构造FOLLOW$(A)$}

                反复应用以下规则:

                \begin{enumerate}
                    \item $\#\in\textrm{FOLLOW}(S)$
                    \item $A\to \alpha B\beta\Rightarrow\textrm{FIRST}(\beta)\subset\textrm{FOLLOW}(B)$, 除$\varepsilon$
                    \item $A\to \alpha B$或$A\to \alpha B\beta$且$\varepsilon\in\textrm{FIRST}(\beta)\Rightarrow\textrm{FOLLOW}(A)\subset\textrm{FOLLOW}(B)$
                \end{enumerate}

            \subsubsection{构造预测分析表的算法}

                $\forall A\to \alpha\in G$, 执行:
                    \begin{itemize}
                        \item $\forall a\in V_T, a\in\mathrm{FIRST}(\alpha)$, $M[A,a]:=A\to \alpha$
                        \item 若$\varepsilon\in\mathrm{FIRST}(\alpha)$, $\forall b\in\mathrm{FOLLOW}(A)$, $M[A,b]:=A\to \alpha$
                    \end{itemize}

                余下没有定义的$M[A,a]$均认为是出错状态.

    \section{LL(1)分析法}

        \textsf{LL(1)分析法}: 从左到右扫描输入串, 最左推导, 分析时一步只向前查看一个符号. LL(1)文法一定可以实现不带回溯的自上而下分析.

        LL(1)分析法的基本思想: 若$A\to a$是产生式并且$a$在FIRST$(\alpha)$中, 当输入符号为$a$时, 语法分析器会用$\alpha$展开$A$. 使用显式栈而不是递归调用来完成分析. 

        \subsection{LL(1)文法的条件}

            文法$G$是LL(1)的, 也就是说$\forall A\in V_N$的任何两个不同产生式$A\to \alpha|\beta$, 有
            \begin{enumerate}
                \item $\textrm{FIRST}(\alpha)\cap\textrm{FIRST}(\beta)=\emptyset$
                \item $\beta\stackrel{*}{\Rightarrow}\varepsilon\Rightarrow\textrm{FIRST}(\alpha)\cap\textrm{FOLLOW}(A)=\emptyset$
            \end{enumerate}

            条件语句文法if-then不能改造成LL(1)文法. 对LL(1)做一些小修改, 则可以支持许多实用编程语言.

        \subsection{执行LL(1)文法}

            \begin{algorithm}
                \caption{执行LL(1)文法}
                \label{algorithm-execute-ll1}
                \begin{algorithmic}[1]
                    \Function{Execute-LL1}{$a$, $A\to \alpha_1|\alpha_2|\cdots|\alpha_n$}
                    \ForAll{$\alpha_i$}
                        \If{$a\in\mathrm{FIRST}(\alpha_i)$}
                            \State \Call{Return}{$\alpha_i$}
                        \EndIf
                    \EndFor
                    \ForAll{$\alpha_i$}
                        \If{$\varepsilon\in\mathrm{FIRST(\alpha_i)}\wedge a\in\mathrm{FOLLOW}(A)$}
                            \State \Call{Return}{$\varepsilon$}
                        \EndIf
                    \EndFor
                    \State \Call{Error}{}
                    \EndFunction
                \end{algorithmic}
            \end{algorithm}

